//幂集。编写一种方法，返回某集合的所有子集。集合中 不包含重复的元素。 
//
// 说明：解集不能包含重复的子集。 
//
// 示例： 
//
// 
// 输入：nums = [1,2,3]
// 输出：
//[
//  [3],
//  [1],
//  [2],
//  [1,2,3],
//  [1,3],
//  [2,3],
//  [1,2],
//  []
//]
// 
//
// Related Topics 位运算 数组 回溯 👍 116 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-08-30 22:39:55
 * @description 面试题 08.04.幂集
 */
public class PowerSetLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PowerSetLcci fun=new PowerSetLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //数字没有给范围，所以需要set去重
	//1.先去重
	//2.或者排序后跳过重复数字
	//3.位运算枚举状态
    public List<List<Integer>> subsets1(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> res=new ArrayList<>();
		backtrack(res,new ArrayList<>(),nums,0);
		return res;
    }
	public void backtrack(List<List<Integer>> res,List<Integer> tempList,int[] nums,int start) {
		res.add(new ArrayList<>(tempList));
		for (int i = start; i < nums.length; i++) {
			if (i > start && nums[i] == nums[i - 1]) continue;//跳过重复数字
			tempList.add(nums[i]);
			backtrack(res, tempList, nums, i + 1);
			tempList.remove(tempList.size() - 1);
		}
	}
	List<Integer> t = new ArrayList<Integer>();
	List<List<Integer>> ans = new ArrayList<List<Integer>>();

	public List<List<Integer>> subsets(int[] nums) {
		int n = nums.length;
		for (int mask = 0; mask < (1 << n); ++mask) {
			t.clear();
			for (int i = 0; i < n; ++i) {
				if ((mask & (1 << i)) != 0) {
					t.add(nums[i]);
				}
			}
			ans.add(new ArrayList<Integer>(t));
		}
		return ans;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
